/*
 * @lc app=leetcode.cn id=322 lang=cpp
 *
 * [322] 零钱兑换
 */

// @lc code=start
#include <bits/stdc++.h>
using namespace std;
class Solution
{
public:
    int coinChange(vector<int> &coins, int amount)
    {
        if(amount == 0) return 0;
        set<int> coins_set;
        int max_coin = 0;
        int min_coin = amount;
        {
            for (auto n : coins)
                if (n <= amount)
                {
                    coins_set.insert(n);
                    max_coin = std::max(max_coin, n);
                    min_coin = std::min(min_coin, n);
                }
            if(coins_set.empty()) return -1;
        }

        if (max_coin == amount)
            return 1;

        vector<int> dp(amount + 1, amount + 1);
        dp[0] = 0;

        for (auto n : coins_set)
            dp[n] = 1;

        for (int i = min_coin; i <= amount; i++)
        {
            for (auto n : coins_set)
            {
                if (i >= n)
                    dp[i] = std::min(dp[i], dp[i - n] + 1);
            }
        }

        if(dp[amount] <= amount) return dp[amount];
        else return -1;
    }
};
// @lc code=end
